문제 https://www.acmicpc.net/problem/4485 Algorithm- 다익스트라 알고리즘 사용했당 Codeimport java.util.*;import java.io.*;public class Main { static class Node implements Comparable{ int x; int y; int cost; public Node(int x, int y, int cost) { this.x = x; this.y = y; this.cost = cost; } @Override public int compareTo(Node o) { return this.cost - o.cost; } } static int n; static int[][]..
전체 글
항공대 알고리즘 동아리 Koala 🥰문제우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.입력사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사..
문제 https://www.acmicpc.net/problem/1759문제바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.새 보안 시스템에서 조교들이 암호로 사용했을 법한 문..
문제 https://www.acmicpc.net/problem/4963 Algorithm Codeimport sysfrom collections import dequeinput = sys.stdin.readlinedx = [0,0,1,-1,1,-1,1,-1]dy = [1,-1,0,0,1,1,-1,-1]def BFS(x,y): queue = deque() queue.append([x,y]) graph[y][x] = 0 while queue: x,y = queue.popleft() for i in range(8): next_x = x + dx[i] next_y = y + dy[i] ..
https://www.acmicpc.net/problem/2583입력첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다. 출력첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다. 문제 코드from collections import dequ..
https://www.acmicpc.net/problem/31575알고리즘좌측상단에서 우측하단까지의 길을 찾는 문제이다. 2차원인 배열을 1차원으로 바꾸어 그래프에 적용하였다. 현재 위치가 1인 상태에서 오른쪽이 1이면 이동가능이므로 그래프에 추가, 아래가 1이면 이동가능이므로 그래프에 추가한 뒤에 dfs를 실행한다.마지막 위치의 visited배열을 검사하여 True면 이동이 가능하므로 Yes를 출력해준다.dfs로 해결했지만, dp로도 풀 수 있는 문제인 것 같다.코드import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**6)def dfs(graph, v, visited): visited[v] = True for i in graph[v]:..
https://school.programmers.co.kr/learn/courses/30/lessons/87694 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr알고리즘 유형깊이/너비 우선 탐색(DFS/BFS)문제 설명다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다. 지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다. 만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다. 단, 서로 다른 두 직사각형의 x축 좌표 또는 y..
문제 https://www.acmicpc.net/problem/16713 Algorithm누적합누적합이 아니라 매번 모든 쿼리를 계산하면 시간 초과가 난다.또한 베타적 논리합(XOR, ⊻)이 결합법칙이 성립함을 알고 있어야 한다.예를 들어 (a1 ⊻ a2 ⊻... a10) = (a1 ⊻ a2) ⊻ (a3 ⊻ a4 ⊻ ... a10) 이다.그리고 A ⊻ B = C 일 때, C ⊻ A = B, C ⊻ B = A 이다.추가적으로 0 ⊻ N = N 임을 알고 있어도 도움이 된다. Codeinput = __import__('sys').stdin.readlineN, Q = map(int, input().rstrip().split())a_list = list(map(int, input().rstrip().spl..
문제 https://www.acmicpc.net/problem/7795문제심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모..
문제 https://www.acmicpc.net/problem/11478 Algorithm1. 처음엔 재귀를 이용해서 앞에서 부터 중복되는 문자열이 있으면 무시하는 방식으로 풀려 했는데 시간 초과 발생 (코드 짜는데 20분)2. Set 이용해서 푸니까 바로 풀림 (코드 짜는데 1분)3. 범위 보고 시간 복잡도 구하고 된다 싶으면 그냥 쉬운 개념 부터 쓰자... Codeimport java.io.*;import java.util.*;public class Main { static HashSet hashSet = new HashSet(); static int ans = 0; public static void main(String args[]) throws IOException { Buffer..
https://www.acmicpc.net/problem/1918문제수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차..
https://www.acmicpc.net/problem/17413알고리즘단어를 뒤집어서 출력하면 되는 문제이다. 하지만, 태그안에 있는 단어는 뒤집지 않아야 한다.단어를 구분하는 기준은 공백과 태그이므로 이를 기준으로 코드를 구성하였다.태그가 들어오면 단어를 뒤집지 말고 출력해야 하므로 스택에 넣지않고 계속 ans에 붙여준다. flag를 설정해서 다음 단어가 태그안에 있다는 것을 표시해주고 태그가 끝나면 flag를 비활성화 해준다.공백이 나오면 stack에 있는 단어들을 ans에 붙여준다.문제에서 문자열의 끝은 공백이 아니므로, 마지막에 한번더 스택을 검사해서 단어를 붙여준다.코드import sysinput = sys.stdin.readlineans = ''stack = []s = input().str..